class Solution {
    // Map<Character, Character> map = new HashMap(){
    //     {
    //         put('(', ')');
    //         put('{', '}');
    //         put('[', ']');
    //     }
    // };

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '(' || c == '{' || c == '[') {
                stack.push(c);
            }else if(!stack.isEmpty()){
                char t = stack.peek();
                if(t == '(' && c == ')'
                        || t == '{' && c == '}'
                        || t == '[' && c == ']') {
                    stack.pop();
                }else {
                    return false;
                }
            }else {
                return false;
            }
        }

        return stack.isEmpty();
    }
}